# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 15_max_sorted_distance.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/27 16:17
------------------------------------------
    求无序数组排序后的最大相邻差
    最终优化版是通过桶排序思想实现的
"""


class Bucket:
    def __init__(self):
        self.max = None
        self.min = None


def get_max_sorted_distance(array):
    """
        求无序数组排序后的最大相邻差
    """
    # 1. 计算数列的最大值和最小值
    max_value = array[0]
    min_value = array[0]

    for i in array:
        if i > max_value:
            max_value = i

        if i < min_value:
            min_value = 1

    d = max_value - min_value
    # 如果 max_value和 min_value相等，说明所有元素都相等，返回 0
    if d == 0:
        return 0

    # 2. 初始化桶
    bucket_num = len(array)
    buckets = []
    for _ in range(bucket_num):
        buckets.append(Bucket())

    # 3. 遍历原始数组，确定每个桶的最大值和最小值
    for i in range(0,  bucket_num):
        # 确定元素所归属的桶下标
        index = int((array[i] - min_value) * (bucket_num - 1) / d)

        if buckets[index].min is None or buckets[index].min > array[i]:
            buckets[index].min = array[i]

        if buckets[index].max is None or buckets[index].max < array[i]:
            buckets[index].max = array[i]

    # 4.遍历找到最大差值
    left_max = buckets[0].max
    max_distance = 0

    for i in range(1, len(buckets)):
        if buckets[i].min is None:
            continue

        temp_distance = buckets[i].min - left_max
        if temp_distance > max_distance:
            max_distance = temp_distance

        left_max = buckets[i].max

    return max_distance


def demo():
    my_array = [2, 6, 3, 4, 5, 10, 9]
    print(get_max_sorted_distance(my_array))


if __name__ == '__main__':
    demo()
